package 每日一题;

import java.util.Arrays;

public class No1482制作m束花所需的最少天数 {

    /**
     * 给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
     * 现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
     * 花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
     * 请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
     *
     * 示例 1：
     * 输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
     * 输出：3
     * 解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
     * 现在需要制作 3 束花，每束只需要 1 朵。
     * 1 天后：[x, _, _, _, _]   // 只能制作 1 束花
     * 2 天后：[x, _, _, _, x]   // 只能制作 2 束花
     * 3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3
     * 示例 2：
     * 输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
     * 输出：-1
     * 解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。
     * 示例 3：
     * 输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
     * 输出：12
     * 解释：要制作 2 束花，每束需要 3 朵。
     * 花园在 7 天后和 12 天后的情况如下：
     * 7 天后：[x, x, x, x, _, x, x]
     * 可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
     * 12 天后：[x, x, x, x, x, x, x]
     * 显然，我们可以用不同的方式制作两束花。
     * 示例 4：
     * 输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
     * 输出：1000000000
     * 解释：需要等 1000000000 天才能采到花来制作花束
     * 示例 5：
     * 输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
     * 输出：9
     *  
     * 提示：
     * bloomDay.length == n
     * 1 <= n <= 10^5
     * 1 <= bloomDay[i] <= 10^9
     * 1 <= m <= 10^6
     * 1 <= k <= n
     */

    public int minDays(int[] bloomDay, int m, int k) {

        if(m*k>bloomDay.length){
            return -1;
        }

        /**
         * 二分法:
         * left: min  right: max
         * 然后开始检验mid是否符合规则;
         * 总结: 一些大区间求结果的题目,可以想到用 区间 二分法!!!~~~
         */

        int left = Arrays.stream(bloomDay).min().getAsInt();
        int right = Arrays.stream(bloomDay).max().getAsInt();
        int mid;

        while (left<right){
            mid=(right-left)/2+left;
            if(isOk(bloomDay,mid,m,k)){
                //当前天数可以,就右边界缩短
                right=mid;
            }else{
                //当前天数不可以,就左边界缩短
                left=mid+1;
            }
        }


        return left;
    }

    private boolean isOk(int[] bloomDay,int day, int m, int k) {

        //检验当前天数是否可以符合 m束花,每束相邻k朵

        int count=0;
        int sum=0;

        for (int i = 0; i < bloomDay.length; i++) {

            if(bloomDay[i]<=day){
                count++;
            }else{
                count=0;
            }
            if(count==k){
                sum++;
                count=0;
                if(sum>=m){
                    return true;
                }
            }
        }

        return sum>=m;
    }

    public static void main(String[] args) {
        No1482制作m束花所需的最少天数 n=new No1482制作m束花所需的最少天数();
        int[] arr={3542,4862,3568,3602,2074,2056,1330,923,2362,4948,1403,1208,5554,2591,2567,4857,266,4274,4995,863,4167,3389,2515,2778,955,5152,4232,4154,2041,5169,574,4786,3096,252,2501,1397,1910,2722,3116,2707,2837,409,488,2048,2546,4196,580,4434,2361,5190,4842,4914,487,3047,1676,3716,737,5378,244,3565,7,3672,4115,3985,123,4708,1701,5649,3961,1138,1254,3692,366,4342,4225,1240,2286,986,4111,1247,2992,5391,4497,1472,241,4530,4416,1842,1590,4607,588,3379,1895,5364,4133,418,1387,5113,3352,4965,4909,2216,1295,4531,4171,3224,5407,1654,3142,4662,444,1538,1431,844,2759,2735,3760,2605,1546,3630,4066,1870,410,3858,480,2389,1905,3553,638,1606,1786,1804,3355,2898,1126,108,908,4194,4782,2619,272,20,5102,4344,3158,1867,2484,1462,4269,1382,2215,3233,3425,3435,401,4660,5201,317,5149,1249,2070,5309,846,2839,1738,3207,1155,4055,702,3625,3561,4486,5652,2224,185,3269,2144,1757,3861,302,3431,5481,2042,2979,3915,3935,1976,1347,1360,3445,1733,3334,1252,5310,1557,4471,4836,993,2441,3554,2204,2884,3645,279,1346,2783,3013,1531,1066,4635,5630,4235,2655,4981,1781,353,3809,382,370,2352,2815,935,634,4329,5396,5420,3199,2868,1583,839,468,5320,5572,4319,4026,1632,3930,682,5059,2066,1078,1225,801,3306,278,52,4287,1857,1214,668,3770,1445,4143,5332,1037,277,4646,1118,4473,5238,3528,2294,246,514,2395,4101,2244,731,2975,973};
        int result = n.minDays(arr, 11, 11);
        System.out.println(result);
    }

}
